//72 字符串编辑
/*
给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可
以将两个字符串变成相同

输入输出样例：
	输入是两个字符串，输出是一个整数，表示最少的步骤

Input: word1 = "horse", word2 = "ros"
Output: 3

在这个样例中，一种最优编辑方法是（1） horse -> rorse （2） rorse -> rose（3） rose -> ros
*/
int minDistance(string word1, string word2)
{
	int m = word1.length(), n = word2.length();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
	for (int i = 0; i <= m; ++i)
	{
		for (int j = 0; j <= n; ++j)
		{
			if (i == 0)
			{
				dp[i][j] = j;
			}
			else if (j == 0)
			{
				dp[i][j] = i;
			}
			else
			{
				dp[i][j] = min(
					dp[i - 1][j - 1] + ((word1[i - 1] == word2[j - 1]) ? 0 : 1),
					min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
			}
		}
	}
	return dp[m][n];
}
